#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@sharp>
#
# Distributed under terms of the MIT license.

"""

"""

from pprint import pprint


from collections import defaultdict


class CrossingNode:
    def __init__(self, value=None):
        self.value = value

        # self.pre  = None
        # self.next = None
        # self.up   = None
        # self.down = None
        self.pre  = self
        self.next = self
        self.up   = self
        self.down = self

    def add_next(self, node):
        self.next = node
        node.pre = self

    def add_down(self, node):
        self.down = node
        node.up = self

    def insert_next(self, node):
        next_next = self.next

        self.next = node
        node.pre = self
        node.next = next_next

    def insert_down(self, node):
        down_down = self.next

        self.down = node
        node.up = self
        node.down = down_down


class DancingLink:
    def __init__(self, matrix):
        self.matrix = matrix
        self.rows = len(matrix)
        self.cols = len(matrix[0])

        self.col_last = [None] * self.cols
        self.row_last = [None] * self.rows

        self.head = CrossingNode()

        self.head.next = self.head
        self.head.pre  = self.head
        self.head.down = self.head
        self.head.up   = self.head


        self.make_crossing_head()

        pprint(self.matrix)

        assert self.head.next is self.col_last[0]
        assert self.head.pre  is self.col_last[-1]

        assert self.head.down is self.row_last[0]
        assert self.head.up is self.row_last[-1]

        self.make_crossing()

        for r in range(self.rows):
            print(self.row_last[r].value)
            print(self.row_last[r].next.value)

        for r in range(self.cols):
            print(self.row_last[r].value)
            print(self.row_last[r].next.value)

    def make_crossing(self):
        for r in range(self.rows):
            for c in range(self.cols):
                value = self.matrix[r][c]
                if value == 0:
                    continue

                node = CrossingNode(value)
                self.row_last[r].insert_next(node)
                self.col_last[c].insert_down(node)

                self.row_last[r] = node
                self.col_last[c] = node

    def make_crossing_head(self):
        self.make_col_heads(self.head)
        self.make_row_heads(self.head)

    def make_col_heads(self, head):
        pre = head
        for c in range(self.cols):
            n = CrossingNode()
            pre.add_next(n)
            pre = n
            self.col_last[c] = n

        n.add_next(head)

    def make_row_heads(self, head):
        pre = head
        for c in range(self.rows):
            n = CrossingNode()
            pre.add_down(n)
            pre = n
            self.row_last[c] = n

        n.add_down(head)



def get_matrix():
    # l = [
    #     [0, 0, 1, 0, 1, 1, 0],
    #     [1, 0, 0, 1, 0, 0, 1],

    #     [0, 1, 1, 0, 0, 1, 0],
    #     [1, 0, 0, 1, 0, 0, 0],

    #     [0, 1, 0, 0, 0, 0, 1],
    #     [0, 0, 0, 1, 1, 0, 1],
    # ]

    l = [
        [0, 1, 0],
        [0, 0, 1],
        [1, 0, 0],
        [1, 1, 0],
        [0, 1, 1],
        [1, 1, 1],
        [0, 0, 0],
    ]

    return l

def test():
    s = DancingLink(get_matrix())

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
